package com.dwliu.sort;

public class HeapSort {

	/**
	 * 堆排序：利用堆的性质，将数组分成"堆+有序区",逐步扩大有序区，减小堆，直至只剩下有序区。
	 * @param a
	 */
	public static void heapSort(int a[]){
		makeMaxHeap(a);
		for (int t:a)
			System.out.print(t+" ");
		System.out.println();
		//将数组分成 堆+有序区
		for(int i=a.length-1; i>0; i--){
			//交换第一个和最后一个
			int temp = a[0];
			a[0] = a[i];
			a[i] = temp;
			
			maxHeapFixDown(a, 0, i);
		}
	}
	
	/**
	 * 构造最大堆，从后往前构造，叶子节点均符合要求，所以不用对其调整
	 * @param a
	 */
	private static void makeMaxHeap(int a[]){
		//调整父节点
		for(int i=a.length/2; i>=0; i--){
			
			maxHeapFixDown(a, i, a.length);
		}
	}
	
	/**
	 * 调整位置i，使其符合堆性质（向下符合）
	 * @param a
	 * @param i
	 */
	private static void maxHeapFixDown(int a[],int i,int n){
		int temp = a[i];//i位置的值
		int j = 2*i+1;
		
		//实际上，就是找到i位置的值，所在的合适位置并赋值，（向下找，满足堆的性质）
		while(j<n) {
			if(j+1<n && a[j+1]>a[j]) // 比较左右子节点的值，看谁大谁小
				j++;
			if(a[j]<temp) // 判断与父节点的大小，如果小于父节点就跳出循环
				break;
			
			a[i] = a[j]; //子节点的值向上移一位
			i = j;
			j = 2*i+1;
		}
		
		a[i] = temp;
	}
	
	
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int a []= {1,6,3,4,5};
		for(int t: a)
			System.out.print(t+" ");
		System.out.println();
		heapSort(a);
		for(int t: a)
			System.out.print(t+" ");
	}

}
